class Solution 
{
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        if (prices.empty())
        {
            return 0;
        }

        int n = prices.size();                                 // 可进行交易的天数
        vector<vector<int>> sell(n, vector<int>(k + 1, 0));    // sell[i][k], 第i天结束, 完成k笔交易售出手上股票所持有的最大收益
        vector<vector<int>> buy(n, vector<int>(k + 1, 0));     // sell[i][k], 第i天结束, 完成k笔交易卖出股票所持有的最大收益

        buy[0][0] = -prices[0], sell[0][0] = 0;                // 第1天边界条件的限定
        for (int i = 1; i <= k; i++)
        {
            buy[0][i] = sell[0][i] = INT_MIN / 2;
        }
        for (int i = 1; i < n; i++)
        {
            buy[i][0] = max(buy[i - 1][0],sell[i - 1][0] - prices[i]);    // buy[i][0]有实际意义,sell[i][0]无实际意义
            for (int j = 1; j <= k; j++)
            {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return *max_element(sell.back().begin(), sell.back().end());
    }
};